1. Field of the Invention
The present invention relates to a motion estimation method using a multilevel successive elimination algorithm and a computer readable recording medium for executing the same method.
2. Description of Related Art
Recently, interests and needs for multimedia data communications field have been increased as image conference system, IMT-2000 terminal, etc. are researched and developed due to rapid progress of information communications technology. Among these multimedia data communications, technical field which has currently get most much interests is just transmitting and receiving of various information via wireless network; and it becomes possible to transmit and receive even a large amount of data as the transmitting and receiving velocity of wireless data is improved.
However, the transfer capability of moving image data is excellent, whereas it is difficult to store, transmit and receive the moving image data as amount of data itself is enormous. Further, since the enormous moving image data is properly processed on the basis of requirements of applications, a higher specification of system for processing the moving image is required.
For overcoming these problems, there has been actively studied a moving image compression algorithm that is a scheme for transforming the enormous moving image data into smaller amount of data. As one example, moving image compression standard proposals that have been studied up to now are MPEG of ISO/IEC and H.26x of ITU-T.
For reference, compression method may be largely classified by lossless compression and loss compression. The lossless compression is a method that is capable of fully reconstructing original signal without incurring any loss at decoder, wherein the reconstructed data is fully identical to the original signal. In contrast, the loss compression is that the reconstructed data is not completely identical to the original data and its compression rate is higher than that of the lossless compression; and therefore, it is generally used in processing image or moving image data.
The moving image data has the characteristics of three redundancies: temporal, spatial, and statistical redundancies.
First of all, the temporal redundancy means a redundancy that exists between continuous frames where luminance values of pixels that exist at the same positions of the continuous frames have statistically similar correlations. This is called “redundancy of interframe”.
Meanwhile, the spatial redundancy is a redundancy that presents within one frame wherein luminance value of a pixel has similar correlation to that of its neighboring pixels. This is called “redundancy of intraframe”.
On the other hand, the statistical redundancy stands for a redundancy between transform codes and is called a redundancy between pixels or redundancy in coding.
By eliminating these three redundancies, it is possible to compress the enormous amount of moving image data into smaller amount of data. That is, discrete cosine transformer (DCT) and quantizer are used to eliminate the spatial redundancies, entropying coding is applied to remove the statistical redundancies, and motion estimation and compensation is utilized to eliminate the temporal redundancies.
Among the compression processes mentioned above, the motion estimation and compensation method for removing the temporal redundancies is largely classified by pixel-based estimation method and block-based estimation method. In general, in case of compressing moving image, the block-based estimation method is widely used compared to the pixel-based estimation method because of various efficient merits in the motion estimation (prediction). This method is called block matching algorithm (BMA).
The BMA may be largely classified by two matching methods: a full search block matching and a fast search block matching.
First, the full search block matching estimation is a scheme that performs matching calculation for all candidate blocks within a preset search range and has an advantage that it can obtain optimized motion vector. However, since this estimation requires a large amount of calculation, it is generally employed in the compression and reconstruction for storage medium compared to real-time moving image compression and transmission.
In contrast, since the fast search block matching motion estimation performs searching process for only part of candidate blocks within a search range, it has a shortcoming that it falls into local minimum. This results in the lowering of image quality and increasing of bit stream. However, the calculation amount thereof is relatively small compared to the full search block matching estimation, thereby making real-time moving image compression and transmission possible. As this fast search block matching motion estimation, there exist 3-step search, hierarchical search, diamond search, etc.
Meanwhile, as more improved motion estimation method, there presents a fast full search block matching motion estimation algorithm which all meets the advantages of both the full searching and fast searching block matching motion estimations. This algorithm provides optimum solution by fully searching and has an advantage that its calculation amount is small compared to the full search block matching motion estimation by deciding as to whether sum of absolute difference (SAD) calculation is done for candidate blocks using sum of average which is smaller than the calculation amount of SAD before the SAD calculation. As this fast full searching motion estimation algorithm, there are successive elimination algorithm (SEA), multilevel SEA (MSEA), and extended SEA (ESEA), etc.
First, the SEA is an algorithm that is applied characteristic of mathematical inequality to scale of motion estimation matching. In other words, the SEA is an algorithm for determining whether or not it would calculate SAD using sum of averages of blocks.
At that time, the relationship of average sum and SAD used in such a calculation may be represented as:|R−M(x,y)|≦SAD(x*,y*)   Eq.(1)
R and M(x,y) in Eq.(1) represent average sums of current frame block and candidate blocks within a search range of a previous frame, respectively. And, SAD(x*,y*) is minimum SAD till a current time for a current block and a candidate block. If the relationship of the average sum and SAD do not meet Eq.(1), then the candidate block at position of (x,y) is eliminated; and a next candidate block is compared to the current block. Otherwise, if the relationship meets Eq.(1), SAD(x,y) between the two blocks is derived and then compared to SAD(x*,y*). As the comparison result, if SAD(x,y) between the two blocks is smaller than SAD(x*,y*), SAD(x*,y*) is updated with SAD(x,y). As such, the SEA algorithm has calculative merits for the motion estimation by determining in advance whether or not it would calculate SAD for candidate blocks.
In the meantime, the MSEA is a scheme that extends the SEA to multilevel. The SEA considers that it depends on the relationship of average sum of blocks and SAD, and then decides whether or not it would derive SAD that needs actually large amount of calculation through the comparison of average sum of small sub-blocks calculated in each level and minimum SAD. With this process, the MSEA is capable of decreasing the amount of calculation because it can eliminate most candidate blocks using the average sum of sub-blocks.
FIGS. 2A and 2B are views showing a fundamental concept of MSEA. Referring to FIG. 2A, the SAD is computed at a level n when |Rn−Mn(x, y)|≦SAD(x, y), wherein the n is a number of level. That is, in the MSEA, an elimination level is computed by comparing average sum of small sub-blocks calculated in each level and minimum SAD based on following equation 2 and the SADs of the elimination levels is not computed. Therefore, large amount of computation SAD can be reduced.|R0−M0(x, y)|≦|R1−M1(x, y)|≦|R2−M2(x, y)|≦|R3−M3(x, y)|≦SAD(x, y)   Eq. 2
In Eq. 2, Rn and Mn(x,y) represent average sums of current frame block and candidate blocks at level n, respectively. And, SAD(x,y) is minimum SA′D.
FIG. 2B is a flowchart showing process of MSEA. Referring to FIG. 2B, in the MSEA, the SAD is only computed when |Rn−Mn(x, y)|≦SAD(x, y). Therefore, large amount of computation SAD for elimination levels is reduced in the MSEA.
On the other hand, ESEA is an algorithm that proposes a scheme that quickly calculates SAD of level 4 in the above-described MSEA.
In particular, in the MSEA having relatively high compression performance, it requires unnecessary calculation when calculating on a level-by-level basis. That is, since the decision whether or not it would calculate SAD of candidate blocks tends to start the algorithm from level 0 always among the multi-levels, there occurs load due to unnecessary calculation which causes by performing the algorithm from level 0 even around of initial SAD position having higher elimination level.
Thus, in the MSEA, there is required a scheme capable of eliminating unnecessary calculation when calculating on a level-by-level basis. The elimination levels exist with similar distribution in the center of the initial SAD position due to spatial correlations. Therefore, if it is possible to know elimination levels of several candidate blocks, elimination levels of remaining candidate blocks can be predicted on the basis of the spatial correlations. Using this characteristics, consequently, there has been required a method that is capable of improving the motion estimation method requiring the large amount of calculation more efficiently.